package net.tp.algo.assignment;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 *
 *
 * @author Trung Phan
 * @see net.tp.algo.assignment
 *
 */
public class Munkres {

    private static final Logger logger = Logger.getLogger(Munkres.class.getName());

    private double[][] cost;
    private boolean[] coveredColumns;
    private boolean[] coveredRows;
    private int m;
    private int n;

    private int[] starAtColumn;
    private int[] starAtRow;
    private int[] primeAtColumn;
    private int[] primeAtRow;

    private double minCost;

    public Munkres(double[][] cost) {
        this(cost, cost.length, cost[0].length);
    }

    public Munkres(double[][] cost, int m, int n) {
        init(cost, m, n);

        if (logger.isLoggable(Level.FINE)) logger.fine("START\n" + this.toString());

        // step 1a
        reduceRows();
        if (logger.isLoggable(Level.FINE)) logger.fine("Step 1:\n" + this);

        // step 1b
        reduceColumns();
        if (logger.isLoggable(Level.FINE)) logger.fine("Step 1:\n" + this);

        // step 2
        starNonAdjacentZeros();
        if (logger.isLoggable(Level.FINE)) logger.fine("Step 2:\n" + this);

        while (/* step 3 */ coverStarredZeros() < Math.min(m, n)) {

            if (logger.isLoggable(Level.FINE)) logger.fine("Step 3:\n" + this);

            while (true) {
                long zeroPoint = findNonCoveredZero();
                if (zeroPoint != -1) {
                    int r = (int)(zeroPoint >>> 32);
                    int c = (int)zeroPoint;
                    if (existStarAtRow(r)) { // step 4
                        primeZero(r, c);
                        coverRow(r);
                        uncoverColumn(starAtRow[r]);
                        if (logger.isLoggable(Level.FINE)) logger.fine("Step 4:\n" + this);
                    }
                    else { // step 6
                        List<Long> path = findAugmentingPath(r, c);
                        augment(path);
                        eraseAllPrimes();
                        uncoverAllRows();
                        uncoverAllColumn();
                        if (logger.isLoggable(Level.FINE)) logger.fine("Step 6:\n" + this);
                        break;
                    }
                }
                else { // step 5
                    reduceMatrix();
                    if (logger.isLoggable(Level.FINE)) logger.fine("Step 5:\n" + this);
                }
            }
        }

        if (logger.isLoggable(Level.FINE)) logger.fine("Step 3 - TERMINATE:\n" + this);

        for (int c = 0; c < n; c++) {
            if (existStarAtColumn(c)) minCost+= cost[starAtColumn[c]][c];
        }

        if (logger.isLoggable(Level.FINE)) logger.fine("Min cost: " + minCost);
    }

    private void init(double[][] cost, int m, int n) {
        this.m = m;
        this.n = n;
        this.cost = new double[m][n];
        for (int r = 0; r < m; r++) {
            this.cost[r] = Arrays.copyOf(cost[r], cost[r].length);
        }

        this.coveredColumns = new boolean[n];
        this.coveredRows = new boolean[m];
        this.starAtColumn = new int[n];
        this.starAtRow = new int[m];
        this.primeAtColumn = new int[n];
        this.primeAtRow = new int[m];

        Arrays.fill(starAtRow, -1);
        Arrays.fill(starAtColumn, -1);
        Arrays.fill(primeAtRow, -1);
        Arrays.fill(primeAtColumn, -1);
    }


    private void reduceMatrix() {
        double min = Double.MAX_VALUE;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (!coveredColumns[c] && !coveredRows[r]) {
                    if (min > cost[r][c]) {
                        min = cost[r][c];
                    }
                }
            }
        }

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (coveredColumns[c] && coveredRows[r]) {
                    cost[r][c] += min;
                }
                else if (!coveredColumns[c] && !coveredRows[r]) {
                    cost[r][c] -= min;
                }
            }
        }

    }


    private List<Long> findAugmentingPath(int primeR, int primeC) {

        List<Long> augmentingPath = new ArrayList<>();
        augmentingPath.add(rc(primeR, primeC));

        while (existStarAtColumn(primeC)) {

            int starC = primeC;
            int starR = starAtColumn[starC];
            augmentingPath.add(rc(starR, primeC));

            assert existPrimeAtRow(starR);

            primeR = starR;
            primeC = primeAtRow[starR];
            augmentingPath.add(rc(primeR, primeC));
        }

        return augmentingPath;

    }

    private void augment(List<Long> augmentingPath) {

        for (int i = 0; i < augmentingPath.size(); i += 2) {
            long point = augmentingPath.get(i);
            int r = (int)(point >>> 32);
            int c = (int)point;
            starZero(r, c);
        }

    }

    /**
     * Step 1a
     */
    private void reduceRows() {
        for (int row = 0; row < m; row++) {
            double min = Double.MAX_VALUE;
            for (int c = 0; c < n; c++) {
                if (min > cost[row][c]) min = cost[row][c];
            }

            if (min != 0) {
                for (int c = 0; c < n; c++) {
                    cost[row][c] -= min;
                }
            }
        }
    }

    /**
     * Step 1b
     */
    private void reduceColumns() {
        for (int column = 0; column < n; column++) {
            double min = Double.MAX_VALUE;
            for (int r = 0; r < m; r++) {
                if (min > cost[r][column]) min = cost[r][column];
            }

            if (min != 0) {
                for (int r = 0; r < m; r++) {
                    cost[r][column] -= min;
                }
            }
        }
    }

    /**
     * Step 2
     */
    private void starNonAdjacentZeros() {
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (cost[r][c] == 0 && starAtRow[r] == -1 && starAtColumn[c] == -1) {
                    starZero(r, c);
                }
            }
        }
    }

    /**
     * Step 3
     *
     * @return number of columns covering the starred zeros
     */
    private int coverStarredZeros() {
        int count = 0;
        for (int c = 0; c < n; c++) {
            if (existStarAtColumn(c)) {
                coverColumn(c);
                count++;
            }
        }
        return count;
    }

    /**
     * Step 4
     * @return the location of a non covered zero, -1 if no zero found.
     */
    private long findNonCoveredZero() {

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (!coveredColumns[c] && !coveredRows[r] && cost[r][c] == 0) {
                    return rc(r, c);
                }
            }
        }

        return -1;
    }





    // Helper methods

    private long rc(int row, int column) {
        return ((long)row) << 32 | column;
    }

    private boolean existStarAtRow(int r) {
        return starAtRow[r] > -1;
    }

    private boolean existStarAtColumn(int column) {
        return starAtColumn[column] > -1;
    }

    private void starZero(int row, int column) {
        starAtRow[row] = column;
        starAtColumn[column] = row;
    }

    private boolean existPrimeAtRow(int row) {
        return primeAtRow[row] > -1;
    }

    private void primeZero(int row, int column) {
        this.primeAtRow[row] = column;
        this.primeAtColumn[column] = row;
    }

    private void coverRow(int r) {
        this.coveredRows[r] = true;
    }

    private void coverColumn(int column) {
        coveredColumns[column] = true;
    }

    private void uncoverRow(int row) {
        coveredRows[row] = false;
    }

    private void uncoverColumn(int column) {
        this.coveredColumns[column] = false;
    }

    private void uncoverAllRows() {
        Arrays.fill(coveredRows, false);
    }

    private void uncoverAllColumn() {
        Arrays.fill(coveredColumns, false);
    }

    private void eraseAllPrimes() {
        Arrays.fill(primeAtRow, -1);
        Arrays.fill(primeAtColumn, -1);
    }




    @Override
    public String toString() {

        StringBuilder topLine = new StringBuilder("┌");
        StringBuilder bottomLine = new StringBuilder("└");
        StringBuilder middleLine = new StringBuilder("│");

        for (int c = 0; c < n; c++) {
            topLine.append(coveredColumns[c] ? "──┬──" : "─────");
            bottomLine.append(coveredColumns[c] ? "──┴──" : "─────");
            middleLine.append(coveredColumns[c] ? "  │  " : "     ");
        }
        topLine.append("┐\n");
        bottomLine.append("┘");
        middleLine.append("│\n");

        StringBuilder builder = new StringBuilder(topLine);

        for (int r = 0; r < m; r++) {
            if (r > 0) builder.append(middleLine);
            StringBuilder line = new StringBuilder(coveredRows[r] ? "├" : "│");
            for (int c = 0; c < n; c++) {
                String number = (coveredRows[r] ? "──╴" : "   ") + Integer.toString((int)cost[r][c]);
                line.append(number.substring(number.length() - 3));
                if (starAtRow[r] == c) line.append(coveredRows[r] ? "*╶" : "* ");
                else if (primeAtRow[r] == c) line.append(coveredRows[r] ? "\'╶" : "\' ");
                else line.append(coveredRows[r] ? "╶─" : "  ");
            }
            line.append(coveredRows[r] ? '┤' : '|').append('\n');

            builder.append(line);
        }
        builder.append(bottomLine);

        return builder.toString();
    }
}
